Міністерство освіти і науки, молоді та спорту України Національний університет «Львівська політехніка» Інститут дистанційного навчання Кафедра СКС
КУРСОВА РОБОТА з дисципліни «Програмування» на тему «Статичні та динамічні структури даних» Варіант № 1  Завдання на курсову роботу: 1. Провести огляд методів структур даних: списків, стеків, стеків, черг, що широко застосовуються у програмуванні. Розглянути їх властивості і практичне значення. 2. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно. 3. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри: кількість порівнянь; кількість обмінів; фактичний час роботи, необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів.  ЗМІСТ 1. СПИСКИ. СОРТУВАННЯ СПИСКІВ, ПОШУК У СПИСКАХ……... 4  2. СТЕКИ…………………………………………………………………… 11  3. ЧЕРГИ ПРОСТІ ТА ЦИКЛІЧНІ……………………………………….. 15  3.1 Прості черги…………………………………………………………….. 15  3.2 Циклічні черги………………………………………………………….. 19  4. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ. 24  ВИСНОВКИ…………………………………………………………………… 31  СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ………………………………… 32   1. СПИСКИ. СОРТУВАННЯ СПИСКІВ, ПОШУК У СПИСКАХ Список – це сукупність елементів, кількість яких може змінюватись в ході виконання програми. При цьому пам’ять для розміщення нового елементу виділяється і вивільняється динамічно по мірі необхідності. Зрозуміло, що для реалізації такого типу даних необхідно використовувати покажчики. Списки можуть реалізовуватись за допомогою одинарних або подвійних зв’язків. В списку з одинарними зв’язками кожен елемент містить покажчик на наступний елемент списку. В списку з подвійними зв’язками кожен елемент містить покажчики на попередній і наступний елемент списку. На сьогоднішній день найбільш часто використовуються списки з подвійними зв’язками. Це визвано тим, що список з подвійними зв’язками можна читати в обох напрямках, такий список легше відновлювати при пошкодженні і при використанні таких списків операції обробки інформації реалізуються простіше. Виходячи із сказаного ми будемо розглядати лише списки з подвійними зв’язками. Основними операціями при роботі з списками є: - додавання елементу до списку; - вилучення елементу із списку; - сортування елементів списку; - пошук елемента списку, що відповідає заданому критерію пошуку. Розглянемо ці операції на прикладі. #include <stdio.h> #include <iostream.h> #include <conio.h> //Шаблон класу список template <class T> class my_list { private: //Покажчик на наступний елемент списку my_list *next; 48 //Покажчик на попередній елемент списку my_list *prev; //Поле даних елементу списку T info; //Поточна кількість елементів, занесених до списку int list_size; public: //Функція визначення адреси наступного елементу списку my_list<T> * get_next() {return next;} //Функція визначення адреси попереднього елементу списку my_list<T> * get_prev() {return prev;} //Функція запису адреси наступного елементу списку my_list<T> * set_next(my_list<T> *a) {return next=a;} //Функція запису адреси попереднього елементу списку my_list<T> * set_prev(my_list<T> *a) {return prev=a;} //Функція додавання елементу до списку void add_elem(my_list<T> *first,T inf); //Функція вилучення елементу із списку void del_elem(my_list<T> *first); //Функція сортування елементів списку за зростанням void sort_elements(my_list<T> *first); //Функція зчитування даних, збережених в елементі списку T get_info() {return info;} //Функція запису даних до елементу списку void set_info(T c) {info=c;return;} //Функція запису розміру списку void set_size(int c) {list_size=c;return;} //Функція зчитування розміру списку int get_size() {return list_size;} //Функція відображення інформаційних полів списку на екрані void print_list(my_list<T> *first); //Функція пошуку заданого значення у списку int b_search(my_list<T> *first,T key); } //Реалізація функції видаленн...